Clustering Social Networks Using Distance%2DPreserving Subgraphs.

An Integrated Framework for Simultaneous Classification and Regression of Time%2DSeries Data.

Efficient Algorithm for Localized Support Vector Machine.

Constrained overlapping clusters minimizing the negative effects of bridge%2Dnodes.

A Matrix Alignment Approach for Collective Classification.

History%2DBased Email Prioritization.

A co%2Dclassification framework for detecting web spam and spammers in social media web sites.
Social media are becoming increasingly popular and have attracted considerable attention from spammers. Using a sample of more than ninety thousand known spam Web sites, we found between 7 % to 18 % of their URLs are posted on two popular social media Web sites, digg.com and delicious.com. In this paper, we present a co-classification framework to detect Web spam and the spammers who are responsible for posting them on the social media Web sites. The rationale for our approach is that since both detection tasks are related, it would be advantageous to train them simultaneously to make use of the labeled examples in the Web spam and spammer training data. We have evaluated the effectiveness of our algorithm on the delicious.com data set. Our experimental results showed that the proposed co-classification algorithm significantly outperforms classifiers that learn each detection task independently.


Measuring the effects of preprocessing decisions and network forces in dynamic network analysis.

Combining statistics and semantics via ensemble model for document clustering.

Detection and Characterization of Anomalies in Multivariate Time Series.

Neural Networks.

Receiver Operating Characteristic.
Abstract. Genetic programming (GP) can automatically fuse given classifiers of diverse types to produce a combined classifier whose Receiver Operating Characteristics (ROC) are better than [Scott et al.1998b]’s “Maximum Realisable Receiver Operating Characteristics” (MRROC). I.e. better than their convex hull. This is demonstrated on a satellite image processing bench mark using Naive Bayes, Decision Trees (C4.5) and Clementine artificial neural networks. 1
Data mining for visual exploration and detection of ecosystem disturbances.
This paper presents a case study on the application of data mining to the problem of detecting ecosystem disturbances from vegetation cover data obtained from satellite observations. We describe two anomaly detection approaches—moving average and random walk—for detecting such events. We also illustrate how clustering can be used to locate similar incidents of disturbance events. Finally, we present a clustering-based framework to aid the visual exploration of ecosystem disturbances from high resolution data. 1.
Maximum Margin Active Learning for Sequence Labeling with Different Length.

A Robust Graph%2DBased Algorithm for Detection and Characterization of Anomalies in Noisy Multivariate Time Series.

A matrix alignment approach for link prediction.
This paper introduces a new discriminative learning technique for link prediction based on the matrix alignment approach. Our algorithm automatically determines the most predictive features of the link structure by aligning the adjacency matrix of a network with weighted similarity matrices computed from node attributes and neighborhood topological features. Experimental results on a variety of network data have demonstrated the effectiveness of this approach. 1
Semi%2Dsupervised learning with data calibration for long%2Dterm time series forecasting.
Many time series prediction methods have focused on single step or short term prediction problems due to the inherent difficulty in controlling the propagation of errors from one prediction step to the next step. Yet, there is a broad range of applications such as climate impact assessments and urban growth planning that require long term forecasting capabilities for strategic decision making. Training an accurate model that produces reliable long term predictions would require an extensive amount of historical data, which are either unavailable or expensive to acquire. For some of these domains, there are alternative ways to generate potential scenarios for the future using computer-driven simulation models, such as global climate and traffic demand models. However, the data generated by these models are currently utilized in a supervised learning setting, where a predictive model trained on past observations is used to estimate the future values. In this paper, we present a semisupervised learning framework for long-term time series forecasting based on Hidden Markov Model Regression. A covariance alignment method is also developed to deal with the issue of inconsistencies between historical and model simulation data. We evaluated our approach on data sets from a variety of domains, including climate modeling. Our experimental results demonstrate the efficacy of the approach compared to other supervised learning methods for longterm time series forecasting.
Link Mining for a Social Bookmarking Web Site.
Social bookmarking tools enable users to save URLs for future reference, to create tags for annotating Web pages, and to share Web pages they found interesting with others. This paper presents a case study on the application of link mining to a social bookmarking Web site called del.icio.us. We investigated the user bookmarking and tagging behaviors and described several approaches to find surprising patterns in the data. We also examined the characteristics that made certain users more popular than others. Finally, we demonstrated the effectiveness of using social bookmarks and tags for predicting mutual ties between users. 1
Outrank a Graph%2DBased Outlier Detection Framework Using Random Walk.

A Prototype%2Ddriven Framework for Change Detection in Data Stream Classification.

Recommendation via Query Centered Random Walk on K%2DPartite Graph.

Exploration of Link Structure and Community%2DBased Node Roles in Network Analysis.
Communities are nodes in a network that are grouped together based on a common set of properties. While the communities and link structures are often thought to be in alignment, it may not be the case when the communities are defined using other external criterion. In this paper we provide a new way to measure the alignment. We also provide a new metric that can be used to estimate the number of communities to which a node is attached. This metric, along with degree, is used to assign a communitybased role to nodes. We demonstrate the usefulness of the community-based node roles by applying them to the influence maximization problem. 1
A Probabilistic Substructure%2DBased Approach for Graph Classification.
The classification of graph based objects is an important challenge from a knowledge discovery standpoint and has attracted considerable attention recently. In this paper, we present a probabilistic substructure-based approach for classifying a graphbased dataset. More specifically, we use a frequent subgraph mining algorithm to construct substructure based descriptors and apply the maximum entropy principle to convert the local patterns into a global classification model for graph data. Empirical studies conducted on real world data sets showed that the maximum entropy substructure-based approach often outperforms existing feature vector methods using
A Probabilistic Substructure%2DBased Approach for Graph Classification.
The classification of graph based objects is an important challenge from a knowledge discovery standpoint and has attracted considerable attention recently. In this paper, we present a probabilistic substructure-based approach for classifying a graphbased dataset. More specifically, we use a frequent subgraph mining algorithm to construct substructure based descriptors and apply the maximum entropy principle to convert the local patterns into a global classification model for graph data. Empirical studies conducted on real world data sets showed that the maximum entropy substructure-based approach often outperforms existing feature vector methods using
Incorporating Background Knowledge for Subjective Rule Evaluation.

Kernel Based Detection of Mislabeled Training Examples.
The problem of identifying mislabeled training examples has been examined in several studies, with a variety of approaches developed for editing the training data to obtain better classifiers. Many of these approaches involve applying an individual or an ensemble of classifiers to the training set and filtering the mislabeled examples based on their consistency with respect to the classifier’s outputs. In this study, we formulate mislabeled detection as an optimization problem and introduce a kernel-based approach for filtering the mislabeled examples. Experimental results using a variety of data sets from the UCI data repository demonstrate the effectiveness of our proposed method, compared to existing nearest-neighbor and ensemble-based filtering schemes. 
Localized Support Vector Machine and Its Efficient Algorithm.
kernel functions to classify data sets with complex decision surfaces. Determining the right parameters of such functions is not only computationally expensive, the resulting models are also susceptible to overfitting due to their large VC dimensions. Instead of fitting a nonlinear model, this paper presents a framework called Localized Support Vector Machine (LSVM), which builds multiple linear SVM models from the training data. Since each model is designed to classify a particular test example, it has high computational cost. To overcome this limitation, we propose an efficient implementation of LSVM, termed Profile SVM (PSVM). PSVM partitions the training examples into clusters and builds a separate linear SVM model for each cluster. Our empirical results show that (1) Both LSVM and PSVM outperform nonlinear SVM on the majority of the evaluated data sets; and (2) PSVM achieves comparable accuracy as LSVM but with significant computational savings. 1
Converting Output Scores from Outlier Detection Algorithms into Probability Estimates.

Frequent Closed Itemset Mining Using Prefix Graphs with an Efficient Flow%2DBased Pruning Strategy.
This paper presents PGMiner, a novel graph-based algorithm for mining frequent closed itemsets. Our approach consists of constructing a prefix graph structure and decomposing the database to variable length bit vectors, which are assigned to nodes of the graph. The main advantage of this representation is that the bit vectors at each node are relatively shorter than those produced by existing vertical mining methods. This facilitates fast frequency counting of itemsets via intersection operations. We also devise several internode and intra-node pruning strategies to substantially reduce the combinatorial search space. Unlike other existing approaches, we do not need to store in memory the entire set of closed itemsets that have been mined so far in order to check whether a candidate itemset is closed. This dramatically reduces the memory usage of our algorithm, especially for low support thresholds. Our experiments using synthetic and real-world data sets show that PGMiner outperforms existing mining algorithms by as much as an order of magnitude and is scalable to very large databases. 1.
Adaptively Routing P2P Queries Using Association Analysis.

Outlier Detection Using Random Walks.

Multistep%2DAhead Time Series Prediction.
Abstract. Multistep-ahead prediction is the task of predicting a sequence of values in a time series. A typical approach, known as multi-stage prediction, is to apply a predictive model step-by-step and use the predicted value of the current time step to determine its value in the next time step. This paper examines two alternative approaches known as independent value prediction and parameter prediction. The first approach builds a separate model for each prediction step using the values observed in the past. The second approach fits a parametric function to the time series and builds models to predict the parameters of the function. We perform a comparative study on the three approaches using multiple linear regression, recurrent neural networks, and a hybrid of hidden Markov model with multiple linear regression. The advantages and disadvantages of each approach are analyzed in terms of their error accumulation, smoothness of prediction, and learning difficulty. 1
Semi%2Dsupervised outlier detection.

A Novel Framework for Incorporating Labeled Examples into Anomaly Detection.
This paper presents a principled approach for incorporating labeled examples into an anomaly detection task. We demonstrate that, with the addition of labeled examples, the anomaly detection algorithm can be guided to develop better models of the normal and abnormal behavior of the data, thus improving the detection rate and reducing the false alarm rate of the algorithm. A framework based on the finite mixture model is introduced to model the data as well as the constraints imposed by the labeled examples. Empirical studies conducted on real data sets show that significant improvements in detection rate and false alarm rate are achieved using our proposed framework. 1
Semi%2DSupervised Clustering with Partial Background Information.

Clustering in the Presence of Bridge%2DNodes.

Semi%2DSupervised Clustering with Partial Background Information.

Hyperclique pattern discovery.
Abstract. Existing algorithms for mining association patterns often rely on the support-based pruning strategy to prune a combinatorial search space. However, this strategy is not effective for discovering potentially interesting patterns at low levels of support. Also, it tends to generate too many spurious patterns involving items which are from different support levels and are poorly correlated. In this paper, we present a framework for mining highly-correlated association patterns called hyperclique patterns. In this framework, an objective measure called h-confidence is applied to discover hyperclique patterns. We prove that the objects in a hyperclique pattern have a guaranteed level of global pairwise similarity to one another as measured by the cosine similarity (uncentered Pearson’s correlation coefficient). Also, we show that the h-confidence measure satisfies a cross-support property which can help efficiently eliminate spurious patterns involving items with substantially different support levels. Indeed, this cross-support property is not limited to hconfidence and can be generalized to some other association measures. In addition, an algorithm called hyperclique miner is proposed to exploit both cross-support and anti-monotone properties of the h-confidence measure for the efficient discovery of hyperclique patterns. Finally, our experimental results show that hyperclique miner can efficiently identify hyperclique patterns, even at extremely low levels of support. Keywords: Association Analysis, Hyperclique Patterns, H-confidence 1.
Hyperclique pattern discovery.
Abstract. Existing algorithms for mining association patterns often rely on the support-based pruning strategy to prune a combinatorial search space. However, this strategy is not effective for discovering potentially interesting patterns at low levels of support. Also, it tends to generate too many spurious patterns involving items which are from different support levels and are poorly correlated. In this paper, we present a framework for mining highly-correlated association patterns called hyperclique patterns. In this framework, an objective measure called h-confidence is applied to discover hyperclique patterns. We prove that the objects in a hyperclique pattern have a guaranteed level of global pairwise similarity to one another as measured by the cosine similarity (uncentered Pearson’s correlation coefficient). Also, we show that the h-confidence measure satisfies a cross-support property which can help efficiently eliminate spurious patterns involving items with substantially different support levels. Indeed, this cross-support property is not limited to hconfidence and can be generalized to some other association measures. In addition, an algorithm called hyperclique miner is proposed to exploit both cross-support and anti-monotone properties of the h-confidence measure for the efficient discovery of hyperclique patterns. Finally, our experimental results show that hyperclique miner can efficiently identify hyperclique patterns, even at extremely low levels of support. Keywords: Association Analysis, Hyperclique Patterns, H-confidence 1.
Local Detection of Selfish Routing Behavior in Ad Hoc Networks.
Reputation mechanisms for detecting and punishing free-riders in ad hoc networks depend on the local detection of selfish behavior. Although naive selfish strategies based on dropping data packets are readily detected, more sophisticated strategies that manipulate ad hoc routing protocols present a greater challenge. In this work we develop a method to distinguish selfish peers from cooperative ones based solely on local observations of AODV routing protocol behavior. Our approach uses the finite state machine model of locally observed AODV actions to build up a statistical description of the behavior of each neighbor. We apply a series of wellknown statistical tests to features derived from this description to partition the set neighboring nodes into a cooperative and selfish class. Simulation results for a non-mobile ad hoc network show that our approach can detect two different types of routing manipulation while maintaining a low rate of false positives. 1
Introduction to Data Mining
Introduction to Data Mining  We are in an age often referred to as the information age. In this information age, because we believe that information leads to power and success, and thanks to sophisticated technologies such as computers, satellites, etc., we have been collecting tremendous amounts of information. Initially, with the advent of computers and means for mass digital storage, we started collecting and storing all sorts of data, counting on the power of computers to help sort through this amalgam of information. Unfortunately, these massive collections of data stored on disparate structures very rapidly became overwhelming. This initial chaos has led to the creation of structured databases and database management systems (DBMS). The efficient database management systems have been very important assets for management of a large corpus of data and especially for effective and efficient retrieval of particular information from a large collection whenever needed. The prol
Local Detection of Selfish Routing Behavior in Ad Hoc Networks.
Reputation mechanisms for detecting and punishing free-riders in ad hoc networks depend on the local detection of selfish behavior. Although naive selfish strategies based on dropping data packets are readily detected, more sophisticated strategies that manipulate ad hoc routing protocols present a greater challenge. In this work we develop a method to distinguish selfish peers from cooperative ones based solely on local observations of AODV routing protocol behavior. Our approach uses the finite state machine model of locally observed AODV actions to build up a statistical description of the behavior of each neighbor. We apply a series of wellknown statistical tests to features derived from this description to partition the set neighboring nodes into a cooperative and selfish class. Simulation results for a non-mobile ad hoc network show that our approach can detect two different types of routing manipulation while maintaining a low rate of false positives. 1
An Incremental Data Stream Clustering Algorithm Based on Dense Units Detection.

Mining interesting contrast rules for a web%2Dbased educational system.
Web-based educational technologies allow educators to study how students learn (descriptive studies) and which learning strategies are most effective (causal/predictive studies). Since web-based educational systems collect vast amounts of student profile data, data mining and knowledge discovery techniques can be applied to find interesting relationships between attributes of students, assessments, and the solution strategies adopted by students. This paper focuses on the discovery of interesting contrast rules, which are sets of conjunctive rules describing interesting characteristics of different segments of a population. In the context of webbased educational systems, contrast rules help to identify attributes characterizing patterns of performance disparity between various groups of students. We propose a general formulation of contrast rules as well as a framework for finding such patterns. We apply this technique to an online educational system developed at Michigan State University called LON-CAPA.
Support envelopes a technique for exploring the structure of association patterns.
This paper introduces support envelopes—a new tool for analyzing association patterns—and illustrates some of their properties, applications, and possible extensions. Specifically, the support envelope for a transaction data set and a specified pair of positive integers (m, n) consists of the items and transactions that need to be searched to find any association pattern involving m or more transactions and n or more items. For any transaction data set with M transactions and N items, there is a unique lattice of at most M ∗ N support envelopes that captures the structure of the association patterns in that data set. Because support envelopes are not encumbered by a support threshold, this support lattice provides a complete view of the association structure of the data set, including association patterns that have low support. Furthermore, the boundary of the support lattice—the support boundary—has at most min(M, N) envelopes and is especially interesting since it bounds the maximum sizes of potential association patterns—not only for frequent, closed, and maximal itemsets, but also for patterns, such as error-tolerant itemsets, that are more general. The association structure can be represented graphically as a two-dimensional scatter plot of the (m, n) values associated with the support envelopes of the data set, a feature that is useful in the exploratory analysis of association patterns. Finally, the algorithm to compute support envelopes is simple and computationally efficient, and it is straightforward to parallelize the process of finding all the support envelopes.


Generalizing the notion of support.
The goal of this paper is to show that generalizing the notion of support can be useful in extending association analysis to non-traditional types of patterns and non-binary data. To that end, we describe a framework for generalizing support that is based on the simple, but useful observation that support can be viewed as the composition of two functions: a function that evaluates the strength or presence of a pattern in each object (transaction) and a function that summarizes these evaluations with a single number. A key goal of any framework is to allow people to more easily express, explore, and communicate ideas, and hence, we illustrate how our support framework can be used to describe support for a variety of commonly used association patterns, such as frequent itemsets, general Boolean patterns, and error-tolerant itemsets. We also present two examples of the practical usefulness of generalized support. One example shows the usefulness of support functions for continuous data. Another example shows how the hyperclique pattern---an association pattern originally defined for binary data---can be extended to continuous data by generalizing a support function.
Ordering patterns by combining opinions from multiple sources.
Pattern ordering is an important task in data mining because the number of patterns extracted by standard data mining algorithms often exceeds our capacity to manually analyze them. A standard approach for handling this problem is to rank the patterns according to an evaluation metric and then presents only the highest ranked patterns to the users. This approach may not be trivial due to the wide variety of metrics available, some of which may lead to conflicting ranking results. In this paper, we present an effective approach to address the pattern ordering problem by combining the rank information gathered from multiple sources. Although rank aggregation techniques have been developed for applications such as meta-search engines, they are not directly applicable to pattern ordering for two reasons. First, the techniques are mostly supervised, i.e., they require a sufficient amount of labeled data. Second, the objects to be ranked are assumed to be independent and identically distributed (i.i.d), an assumption that seldom holds in pattern ordering. The method proposed in this paper is an adaptation of the original Hedge algorithm, modified to work in an unsupervised learning setting. Techniques for addressing the i.i.d. violation in pattern ordering are also presented. Experimental results demonstrate that our unsupervised Hedge algorithm outperforms many alternative techniques such as those based on weighted average ranking and singular value decomposition.
HICAP Hierarchical Clustering with Pattern Preservation.

RBA An Integrated Framework for Regression based on Association Rules.

Selecting the right objective measure for association analysis.

Mining Strong Affinity Association Patterns in Data Sets with Skewed Support Distribution.
Existing association-rule mining algorithms often rely on the support-based pruning strategy to prune its combinatorial search space. This strategy is not quite effective for data sets with skewed support distributions because they tend to generate many spurious patterns involving items from different support levels or miss potentially interesting low-support patterns. To overcome these problems, we propose the concept of hyperclique pattern, which uses an objective measure called h-confidence to identify strong affinity patterns. We also introduce the novel concept of crosssupport property for eliminating patterns involving items with substantially different support levels. Our experimental results demonstrate the effectiveness of this method for finding patterns in dense data sets even at very low support thresholds, where most of the existing algorithms would break down. Finally, hyperclique patterns also show great promise for clustering items in high dimensional space.
Discovery of climate indices using clustering.
To analyze the effect of the oceans and atmosphere on land climate, Earth Scientists have developed climate indices, which are time series that summarize the behavior of selected regions of the Earth’s oceans and atmosphere. In the past, Earth scientists have used observation and, more recently, eigenvalue analysis techniques, such as principal components analysis (PCA) and singular value decomposition (SVD), to discover climate indices. However, eigenvalue techniques are only useful for finding a few of the strongest signals. Furthermore, they impose a condition that all discovered signals must be orthogonal to each other, making it difficult to attach a physical interpretation to them. This paper presents an alternative clustering-based methodology for the discovery of climate indices that overcomes these limitations and is based on clusters that represent regions with relatively homogeneous behavior. The centroids of these clusters are time series that summarize the behavior of the ocean or atmosphere in those regions. Some of these centroids correspond to known climate indices and provide a validation of our methodology; other centroids are variants of known indices that may provide better predictive power for some land areas; and still other indices may represent potentially new Earth science phenomena. Finally, we show that cluster based indices generally outperform SVD derived indices, both in terms of area weighted correlation and direct correlation with the known indices.
Selecting the right interestingness measure for association patterns.
Many techniques for association rule mining and feature selection require a suitable metric to capture the dependencies among variables in a data set. For example, metrics such as support, confidence, lift, correlation, and collective strength are often used to determine the interestinghess of association patterns. However, many such measures provide conflicting information about the interestinghess of a pattern, and the best metric to use for a given application domain is rarely known. In this paper, we present an overview of various measures proposed in the statistics, machine learning and data mining literature. We describe several key properties one should examine in order to select the right measure for a given application domain. A comparative study of these properties is made using twenty one of the existing measures. We show that each measure has different properties which make them useful for some application domains, but not for others. We also present two scenarios in which most of the existing measures agree with each other, namely, support-based pruning and table standardization. Finally, we present an algorithm to select a small set of tables such that an expert can select a desirable measure by looking at just this small set of tables.
High Performance Data Mining.
Abstract. Recent times have seen an explosive growth in the availability of various kinds of data. It has resulted in an unprecedented opportunity to develop automated data-driven techniques of extracting useful knowledge. Data mining, an important step in this process of knowledge discovery, consists of methods that discover interesting, non-trivial, and useful patterns hidden in the data [SAD+93, CHY96]. The field of data mining builds upon the ideas from diverse fields such as machine learning, pattern recognition, statistics, database systems, and data visualization. But, techniques developed in these traditional disciplines are often unsuitable due to some unique characteristics of today’s data-sets, such as their enormous sizes, high-dimensionality, and heterogeneity. There is a necessity to develop effective parallel algorithms for various data mining techniques. However, designing such algorithms is challenging, and the main focus of the paper is a description of the parallel formulations of two important data mining algorithms: discovery of association rules, and induction of decision trees for classification. We also briefly discuss an application of data mining to the analysis of large data sets collected by Earth observing satellites that need to be processed to better understand global scale changes in biosphere processes and patterns. 1
Discovery of Web Robot Sessions Based on their Navigational Patterns.
Web robots are software programs that automatically traverse the hyperlink structure of the World Wide Web in order to locate and retrieve information. There are many reasons why it is important to identify visits by the Web robots and distinguish them from other users. First of all, e-commerce retailers are particularly concerned about the unauthorized deployment of robots for gathering business intelligence at their Web sites. In addition, Web robots tend to consume considerable network bandwidth at the expense of other users. Sessions due to Web robots also make it more difficult to perform clickstream analysis effectively on the Web data. Conventional techniques for detecting Web robots are often based on identifying the IP address and user agent of the Web clients. While these techniques are applicable to many well-known robots, they may not be sufficient to detect camouaging and previously unknown robots. In this paper, we propose an alternative approach that uses the navigational patterns in the click-stream data to determine if it is due to a robot. Experimental results on our Computer Science department Web server logs show that highly accurate classification models can be built using this approach. We also show that these models are able to discover many camouflaging and previously unidentified robots.
Mining Indirect Associations in Web Data.

Textual data mining of service center call records.

Indirect Association Mining Higher Order Dependencies in Data.
This paper introduces a novel pattern called indirect association and examines its utility in various application domains. Existing algorithms for mining associations, such as Apriori, will only discover itemsets that have support above a user-defined threshold. Any itemsets with support below the minimum support requirement are filtered out. We believe
Web Usage Mining Discovery and Applications of Usage Patterns from Web Data.

Discovery of Interesting Usage Patterns from Web Data.

